package algorithm_demo.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 402. 移掉 K 位数字
 * <a href="https://leetcode.cn/problems/remove-k-digits/">https://leetcode.cn/problems/remove-k-digits/</a>
 * 单调栈
 * @author Api
 * @date 2023/5/10 23:11
 */
public class Problem_402_RemoveKDigits {
    public static String removeKdigits(String num, int k) {
        if (k == num.length()){
            return "0";
        }
        Deque<Character> stack = new ArrayDeque<>();
        char[] charNum = num.toCharArray();
        int i = 0;
        while(i < charNum.length){
            while(k>0 && !stack.isEmpty() && charNum[i] < stack.peek()){
                stack.pop();
                k--;
            }
            stack.push(charNum[i]);
            i++;
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pollLast());
        }

        String ans = sb.toString();
        //处理k有剩余的情况
        if (k != 0){
            ans = ans.substring(0, ans.length()-k);
        }
        //处理前导0
        int j = 0;
        while(j < ans.length() && ans.charAt(j) == '0'){
            j++;
        }
        //全是0的情况
        if(j == ans.length()) {
            return "0";
        }
        ans = ans.substring(j);
        return ans;
    }

    public static void main(String[] args) {
        removeKdigits("10200", 6);
    }
}
